Birthday Paradox

Like many things which are named a paradox in mathematics, the birthday paradox is not a paradox at all, but rather a probability problem which has a solution often considered unintuitive.

As is common with this problem, we make the simplifications that the probability of an individual having a given birthday is as likely as any other birthday, and that there are exactly $365$ days every year.

We choose to identify each date with an element in the set $\mathbb{Z}/365\mathbb{Z}$, and hence an outcome for the birthdays of all $n$ people with an element in $(\mathbb{Z}/365\mathbb{Z}{)}^n$.

We know that there are $|(\mathbb{Z}/365\mathbb{Z}{)}^n|={365}^n$ total outcomes of equal likelihood.

Now, to count the number of outcomes in which no two people share the same birthday, we are counting the number of ways of selecting $n$ elements from $\mathbb{Z}/365\mathbb{Z}$ without repetition where order is important.

This is exactly ${}^{365}{P}_n=\frac{365!}{(365-n)!}$.

Hence, given all outcomes are of equal likelihood, the probability of an event in which no two people share a common birthday out of $n$ people is:

Hence the probability that any two people have the same birthday out of $n$ people is the complementary event of the above, and hence has probability:

The smallest value of $n$ for this expression to exceed $\frac{1}{2}$ is $23$.